package main

import (
	"fmt"
)

/**
执行用时：64 ms, 在所有 Go 提交中击败了24.56%的用户
内存消耗：17.6 MB, 在所有 Go 提交中击败了56.29%的用户
 */

type Trie struct {
	is_end bool
	son [26]*Trie
}

func Constructor() Trie {
	res := Trie{}

	res.is_end = false
	for i := 0; i < 26; i++ { res.son[i] = nil }

	return res
}

func (this *Trie) Insert(word string) {
	p := this
	for _, c := range word {
		u := c - 'a'
		if p.son[u] == nil {
			t := Constructor();
			p.son[u] = &t
		}
		p = p.son[u]
	}
	p.is_end = true
}

func (this *Trie) Search(word string) bool {
	p := this
	for _, c := range word {
		u := c - 'a'
		if p.son[u] == nil { return false }
		p = p.son[u]
	}
	return p.is_end
}

func (this *Trie) StartsWith(prefix string) bool {
	p := this
	for _, c := range prefix {
		u := c - 'a'
		if p.son[u] == nil { return false }
		p = p.son[u]
	}
	return true
}

func main() {

	obj := Constructor()
	obj.Insert("apple")
	fmt.Println(obj.Search("apple"))  // true
	fmt.Println(obj.Search("app"))  // false
	obj.Insert("app")
	fmt.Println(obj.Search("app"))  // true
}
